package com.leetcode;


import com.leetcode.support.TreeNode;

/**
 * 1026. 节点与其祖先之间的最大差值 (中等)
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 */
public class LeetCode1026 {

    public static void main(String[] arg0) {
        Object[] data = new Object[]{8, 3, 10, 1, 6, null, 14, null, null, 4, 7, null, null, 13, null};
        System.out.println("节点与其祖先之间的最大差值 = " + maxAncestorDiff(new TreeNode(data)));
    }

    public static int maxAncestorDiff(TreeNode root) {
        return calculate(root, root.val, root.val);
    }

    public static int calculate(TreeNode current, int min, int max) {
        if (current == null || !current.isValidVal()) {
            return 0;
        }
        int maxDiff = Math.max(Math.abs(current.val - min), Math.abs(current.val - max));
        min = Math.min(min, current.val);
        max = Math.max(max, current.val);
        maxDiff = Math.max(maxDiff, calculate(current.left, min, max));
        maxDiff = Math.max(maxDiff, calculate(current.right, min, max));
        return maxDiff;
    }

}
